#include <math.h>
#include <stdlib.h>
#include "util/algorithm.h"
#include "map_display.h"
#include "world/map.h"
#include "generator/layout.h"
#include "resources/resources.h"
#include "dark_blit.h"

static void map_decorate (MapDisplay* d);
static void gfx_tile_xy (MapDisplay* d, int sheet, int handle, int frames, int* x, int* y);
static void gfx_obj_xy (MapDisplay* d, int handle, int* x, int* y);
static void light_init (MapDisplay* d, int capacity);
static void light_cleanup (MapDisplay* d);
static int map_index_light (Map* m, int x, int y, int z);
static int light_table_index (int x, int y);
static LightTable* light_make_table (MapDisplay* d, Coord where);

/*
 * Initializes the MapDisplay. Also chooses graphics for all map tiles.
 */
void map_display_init (MapDisplay* d, Map* m) 
{
	assert(d != NULL);
	assert(m != NULL);
	
	memset (d, 0, sizeof(MapDisplay));
	d->map = m;
	int memsize = m->layers * sizeof(BITMAP*);
	d->tiles = malloc (memsize);
	memset (d->tiles, 0, memsize);
	
	map_decorate (d);
	
	for (int i = 0; i < m->layers; i++) {
		d->tiles[i] = bmp.tileset[i % TILESET_COUNT];
	}
	d->objects = bmp.objects;
	
	light_init (d, LIGHTMEMPOOL_SIZE / (sizeof(LightTable) + LIGHTTABLE_SIZE));
}

void map_display_cleanup (MapDisplay* d)
{
	assert(d != NULL);
	
	light_cleanup (d);
	free (d->tiles);
	memset (d, 0, sizeof(MapDisplay));
}

void map_display_set_observer (MapDisplay* display, Coord observer)
{
	display->observer = observer;
	display->offset_x = DISPLAY_WIDTH/2 - observer.x;
	display->offset_y = DISPLAY_HEIGHT/2 - observer.y;
}

void map_display_bg (MapDisplay* d, BITMAP* target)
{
	Map* m = d->map;
	int z = d->observer.z;
	assert((z >= 0) && (z < m->layers));
	
	// bounds in tile units of on-screen visible map
	int min_x = MAX (0, (-(d->offset_x) / TILE_SIZE));
	int min_y = MAX (0, (-(d->offset_y) / TILE_SIZE));
	int max_x = MIN ( m->width , ((-d->offset_x+target->w) / TILE_SIZE) +1 );
	int max_y = MIN ( m->height, ((-d->offset_y+target->h) / TILE_SIZE) +1 );

	BITMAP* tiles = d->tiles[z];

	// Draw all tiles, each consists of 4 subtiles
	for (int y = min_y; y < max_y; y++)
	for (int x = min_x; x < max_x; x++) {
		Tile* t = &TILE(m,x,y,z);
		
		for (int i = 0; i < SUBTILES; i++) {
			int stx = i % SUB_RES; // subtile x coord counter
			int sty = i / SUB_RES; // subtile y coord counter
			int sheet_x, sheet_y; // x, y of the (sub-)tile in the tileset
			gfx_tile_xy (d, z, t->gfx_back[i], t->n_frames_back, &sheet_x, &sheet_y);
			Coord middle = { 
				x * TILE_SIZE + stx * LTILE_SIZE + LTILE_SIZE/2,
				y * TILE_SIZE + sty * LTILE_SIZE + LTILE_SIZE/2,
				z
			};
			int darkness = map_display_get_darkness (d, middle);
			int target_x = d->offset_x + x * TILE_SIZE + stx * LTILE_SIZE;
			int target_y = d->offset_y + y * TILE_SIZE + sty * LTILE_SIZE;
			
			// floor
			dark_blit (tiles, target, 
			           (x%2) * TILE_SIZE + stx * LTILE_SIZE, 
			           (y%2) * TILE_SIZE + sty * LTILE_SIZE,
			           target_x, target_y,
			           LTILE_SIZE, LTILE_SIZE, darkness);
			
			// actual tile gfx
			dark_blit (tiles, target, sheet_x, sheet_y, target_x, target_y,
			           LTILE_SIZE, LTILE_SIZE, darkness);
		}
	}
}

void map_display_objects (MapDisplay* d, BITMAP* target)
{
	Map* m = d->map;
	int z = d->observer.z;
	assert((z >= 0) && (z < m->layers));
	
	// bounds in tile units of on-screen visible map
	int min_x = MAX (0, -d->offset_x / TILE_SIZE);
	int min_y = MAX (0, -d->offset_y / TILE_SIZE);
	int max_x = MIN ( m->width , ((-d->offset_x+target->w) / TILE_SIZE) +1 );
	int max_y = MIN ( m->height, ((-d->offset_y+target->h) / TILE_SIZE) +1 );

	// Draw objects from all visible tiles
	for (int y = min_y; y < max_y; y++)
	for (int x = min_x; x < max_x; x++) {
		Tile* t = &TILE(m,x,y,z);
		if (!t->has_object) continue;
		
		MapObject* o = t->object;
		int sheet_x, sheet_y;
		gfx_obj_xy (d, o->image, &sheet_x, &sheet_y);
		
		Coord middle = {
			x * TILE_SIZE + TILE_SIZE / 2,
			y * TILE_SIZE + TILE_SIZE / 2,
			z
		};
		int darkness = map_display_get_darkness (d, middle);
		int target_x = d->offset_x + x * TILE_SIZE;
		int target_y = d->offset_y + y * TILE_SIZE;
		dark_blit (d->objects, target, sheet_x, sheet_y, target_x, target_y, 
		           TILE_SIZE, TILE_SIZE, darkness);
	}
}

void map_display_character (MapDisplay* display, Actor *p)
{
	assert(p != NULL);
	assert(p->type == ACTOR_CHARACTER);
	assert(p->character != NULL);
	
	// set target draw coords to top left of sprite
	Coord pos = actor_pxpos (p);
	pos.x += display->offset_x - SPRITE_W/2;
	pos.y += display->offset_y + TILE_SIZE/2 - SPRITE_H;
	
	// source draw coords (on sprite sheet)
	int   px_x,   px_y; // pixel offset
	int tile_x, tile_y; // added to px coords
	int  bmp_w,  bmp_h;
	px_x = px_y = tile_x = tile_y = bmp_w = bmp_h = 0;
	
	switch (p->dir) {
		default:
		case DIR_DOWN : tile_y = 0; break;
		case DIR_UP   : tile_y = 1; break;
		case DIR_LEFT : tile_y = 2; break;
		case DIR_RIGHT: tile_y = 3; break;
	}
	
	switch (p->action.type) {
		default:
		case ACTION_NONE:
		case ACTION_MOVE:
		case ACTION_HALT:
		case ACTION_TRAVERSE:
		case ACTION_RESPAWN:
			tile_x = p->gfx.frame % 8;
			px_x = 0;
			px_y = 0;
			bmp_w = 16;
			bmp_h = 24;
			break;
			
		case ACTION_ATTACK_CLOSE:
		case ACTION_ATTACK_RANGE:
			tile_x = p->gfx.frame % 3;
			px_x = 0;
			px_y = 24*5;
			bmp_w = bmp_h = 64;
			pos.x += SPRITE_SIZE/2 - 32;
			pos.y += SPRITE_SIZE/2 - 24;
			break;

		case ACTION_DIE:
			tile_y = 0; // DIE always has the char looking down
			tile_x = 4 + MIN (p->gfx.frame, 11);
			px_x = 0;
			px_y = 4*24;
			bmp_w = 16;
			bmp_h = 24;
			break;
	}
	
	masked_blit (bmp.player[p->character->type-1], buffer, 
	             px_x + tile_x * bmp_w, px_y + tile_y * bmp_h,
	             pos.x, pos.y - P_OFFSET, bmp_w, bmp_h);
}

void map_display_monster (MapDisplay* display, Actor *m)
{
	assert(m != NULL);
	assert(m->type == ACTOR_MONSTER);
	assert(m->monster != NULL);
	
	// set target draw coords to top left of sprite
	// as opposed to players, monsters are always drawn
	// exactly centered on their current tile position.
	Coord pos = actor_pxpos (m);
	int bmp_wh = SPRITE_SIZE; // TODO: variable size monsters
	pos.x += display->offset_x - bmp_wh/2;
	pos.y += display->offset_y - bmp_wh/2;

	int tile_x, tile_y; // anim frame "tile" from the source sprite sheet
	tile_x = tile_y = 0;

	switch (m->dir) {
		default:
		case DIR_DOWN : tile_y = 0; break;
		case DIR_UP   : tile_y = 1; break;
		case DIR_LEFT : tile_y = 2; break;
		case DIR_RIGHT: tile_y = 3; break;
	}

	switch (m->action.type) { // allow for action-specific frames

	case ACTION_NONE:
	case ACTION_HALT:
	case ACTION_DIE:
		tile_x = 0;
		break;
	case ACTION_ATTACK_CLOSE:
	case ACTION_ATTACK_RANGE:
		tile_x = 4;
		break;
	case ACTION_MOVE:
		tile_x = m->gfx.frame % 4;
		break;

	default:
		assert(0);

	}

	masked_blit (bmp.monster, buffer,
	             tile_x * bmp_wh, // TODO: save monster sheet offset
	             tile_y * bmp_wh, // TODO: save monster sheet offset
	             pos.x, pos.y - P_OFFSET, bmp_wh, bmp_wh);
}

void map_display_fg (MapDisplay* d, BITMAP* target)
{
	Map* m = d->map;
	int z = d->observer.z;
	assert((z >= 0) && (z < m->layers));
	
	// bounds in tile units of on-screen visible map
	int min_x = MAX (0, -d->offset_x / TILE_SIZE);
	int min_y = MAX (0, -d->offset_y / TILE_SIZE);
	int max_x = MIN ( m->width , ((-d->offset_x+target->w) / TILE_SIZE) +1 );
	int max_y = MIN ( m->height, ((-d->offset_y+target->h) / TILE_SIZE) +1 );

	BITMAP* tiles = d->tiles[z];
	
	// Draw all the fg tiles, each consists of 4 subtiles
	for (int y = min_y; y < max_y; y++)
	for (int x = min_x; x < max_x; x++) {
		Tile* t = &TILE(m,x,y,z);
		int tx, ty; // x, y of the tile in the tileset
		
		for (int i = 0; i < 4; i++) {
			int stx = i % SUB_RES; // subtile x coord counter
			int sty = i / SUB_RES; // subtile y coord counter
			gfx_tile_xy (d, z, t->gfx_wallfg[i], 1, &tx, &ty); // fg gfx are never animated    
			Coord middle = { 
				x * TILE_SIZE + stx * LTILE_SIZE + LTILE_SIZE/2,
				y * TILE_SIZE + sty * LTILE_SIZE + LTILE_SIZE/2,
				z
			};
			int darkness = map_display_get_darkness (d, middle);
			int target_x = d->offset_x + x * TILE_SIZE + stx * LTILE_SIZE;
			int target_y = d->offset_y + y * TILE_SIZE + sty * LTILE_SIZE;
			dark_blit (tiles, target, tx, ty, 
			           target_x, target_y, 
			           LTILE_SIZE, LTILE_SIZE, darkness);
	
			#if TOWERHACK_DEBUG
			int tile_x, tile_y, subtile;
			mouse_get_coords (NULL, NULL, NULL, NULL, &tile_x, &tile_y, &subtile);
			if ((x == tile_x) && (y == tile_y) && (i == subtile)) {
				rect(target, target_x, target_y,
				     target_x+LTILE_SIZE-1, target_y+LTILE_SIZE-1, makecol(0,255,0));
			}
			#endif
		}
	}
	
	// Foreground effects 
	for (int i = 0; i < MAX_EFFECTS; i++) {
		Effect* e = &d->effect[i];
		if ((e->cooldown > 0) && (e->coord.z == d->observer.z)) {
			Coord middle = { e->coord.x * TILE_SIZE + TILE_SIZE/2,
			                 e->coord.y * TILE_SIZE + TILE_SIZE/2,
			                 e->coord.z };
			int darkness = map_display_get_darkness (d, middle);
			effect_draw_fg (e, target, d->offset_x, d->offset_y - P_OFFSET, darkness);
		}
	}
}

void map_display_add_effect (MapDisplay* d, Effect e)
{
	d->effect[d->next_effect++ % MAX_EFFECTS] = e;
}

uint8_t map_display_get_darkness (MapDisplay* d, Coord target)
{
	LightTable* gettbl (Coord ltcoords) // coords in light tile units
	{
		if (ltcoords.x < 0) return NULL;
		if (ltcoords.y < 0) return NULL;
		if (ltcoords.x >= d->map->width  * SUB_RES) return NULL;
		if (ltcoords.y >= d->map->height * SUB_RES) return NULL;
		
		int idx = map_index_light (d->map, XYZ(ltcoords));
		if (d->light.table[idx] == NULL) {
			return light_make_table (d, ltcoords);
		} else {
			return d->light.table[idx];
		}
	}
	
	uint8_t getval (LightTable* tbl, Coord target) // coords in light tile units
	{
		int rel_x = target.x - tbl->where.x;
		int rel_y = target.y - tbl->where.y;
		
		if (rel_x < -LIGHTTABLE_WH/2) return 255;
		if (rel_x >  LIGHTTABLE_WH/2) return 255;
		if (rel_y < -LIGHTTABLE_WH/2) return 255;
		if (rel_y >  LIGHTTABLE_WH/2) return 255;
		
		int idx = light_table_index (rel_x, rel_y);
		return tbl->value[idx];
	}
	
	Coord obsct[4]; // Obs interpolation coords in light tiles
	Coord tgtct[4]; // Target interpolation coords in light tiles
	Coord obscp[4]; // Obs interpolation coords in pixels
	Coord tgtcp[4]; // Target interpolation coords in pixels
	LightTable* obstbl[4]; // observer points we are going to interpolate
	int darkpt[16]; // 4 targets in 4 lighttables each interpolated
	int darkwgt[16]; // Weight of each of the points (/distance to obs/tgt)

	// find surrounding light tiles for observer and target
	for (int i = 0; i < 4; i++) {
		int px_xoffset = (i%2) ? LTILE_SIZE/2-1 : -LTILE_SIZE/2;
		int px_yoffset = (i/2) ? LTILE_SIZE/2-1 : -LTILE_SIZE/2;
		obsct[i] = (Coord) {
			(d->observer.x + px_xoffset) / LTILE_SIZE,
			(d->observer.y + px_yoffset) / LTILE_SIZE,
			d->observer.z 
		};
		tgtct[i] = (Coord) {
			(target.x + px_xoffset) / LTILE_SIZE,
			(target.y + px_yoffset) / LTILE_SIZE,
			target.z 
		};
		obscp[i] = (Coord) {
			obsct[i].x * LTILE_SIZE + LTILE_SIZE/2,
			obsct[i].y * LTILE_SIZE + LTILE_SIZE/2,
			obsct[i].z
		};
		tgtcp[i] = (Coord) {
			tgtct[i].x * LTILE_SIZE + LTILE_SIZE/2,
			tgtct[i].y * LTILE_SIZE + LTILE_SIZE/2,
			tgtct[i].z
		};
		obstbl[i] = gettbl (obsct[i]);
	}
		
	#define I (i*4+j)
	for (int i = 0; i < 4; i++)
	for (int j = 0; j < 4; j++) {
		darkpt[I] = obstbl[i] ? getval (obstbl[i], tgtct[j]) : 255;
		
		int observer_x_weight = LTILE_SIZE - abs(d->observer.x - obscp[i].x);
		int observer_y_weight = LTILE_SIZE - abs(d->observer.y - obscp[i].y);
		int target_x_weight = LTILE_SIZE - abs(target.x - tgtcp[j].x);
		int target_y_weight = LTILE_SIZE - abs(target.y - tgtcp[j].y);
		
		darkwgt[I] = 0x400 * ( observer_x_weight * target_x_weight *
		                       observer_y_weight * target_y_weight ) /
		                     ( LTILE_SIZE*LTILE_SIZE*LTILE_SIZE*LTILE_SIZE );
	}
	#undef I
	
	int darksum = 0;
	int weightsum = 0;
	for (int i = 0; i < 16; i++) {
		darksum += darkpt[i] * darkwgt[i];
		weightsum += darkwgt[i];
	}
	
	return darksum/weightsum;
}

/*
 * Every tile on a map has an array of gfx_back and gfx_wallfg.
 * This function fills these members with handles pointing to the
 * tile in the tileset to be drawn at the coordinates of the respective
 * tile. The handles are tileset-independant (in every tileset, 
 * equivalent tile graphics are located at the same x/y position) and
 * determined based on the type, blocking flag and other information
 * about the tile. For example, a TILE_STANDARD that is blocking next to
 * a reular floor tile will get wall graphics.
 * Also decorates map objects.
 */
static void map_decorate (MapDisplay* d) 
{		
	Map* m = d->map;
	
	for (int z = 0; z < m->layers; z++)
	for (int y = 0; y < m->height; y++)
	for (int x = 0; x < m->width;  x++) {
		Tile* t = &TILE(m,x,y,z);
		for (int i = 0; i < 4; i++) {
			t->gfx_back[i] = 18*10 -1; // transparent
			t->gfx_wallfg[i] = 18*10 -1;
		}
		t->n_frames_back = 1;
		
		// wall info on neighboring tiles
		#define IFWALL(X,Y,Z) ((((X) >= 0) && ((Y) >= 0) && ((X) < m->width) && ((Y) < m->height)) ? \
			(TILE(m,(X),(Y),(Z)).blocks_players) : 1)
		int adj[8] = { IFWALL(x-1,y-1,z), 
							IFWALL(x  ,y-1,z),
							IFWALL(x+1,y-1,z),
							IFWALL(x-1,y  ,z),
							IFWALL(x+1,y  ,z),
							IFWALL(x-1,y+1,z),
							IFWALL(x  ,y+1,z),
							IFWALL(x+1,y+1,z) };
		
		// if not wall, this tile might need foreground wall pieces
		if ((!t->blocks_players) && (adj[6])) {
			if (adj[5]) TILE(m,x,y,z).gfx_wallfg[2] = 5;
			else        TILE(m,x,y,z).gfx_wallfg[2] = 4;
			
			if (adj[7]) TILE(m,x,y,z).gfx_wallfg[3] = 5;
			else        TILE(m,x,y,z).gfx_wallfg[3] = 6;
		}
		
		switch (t->type) {
			
		case TILE_COMMON:
		case TILE_CHANGELING: // TODO: handle changeling tiles properly
			if (t->blocks_players) { // TODO: only walls can block ghosts?
				     if (!adj[6] && !adj[3]) t->gfx_back[0] = 18*2 +4;
				else if (!adj[3])            t->gfx_back[0] = 18   +4;
				else if (!adj[0] &&  adj[1]) t->gfx_back[0] = 18*3 +7;
				              
				      
				if (adj[3] && adj[4] && !adj[6]) {
					// Special case: use a full 16x16 wall
					t->gfx_back[0] = 18*6 +6;
					t->gfx_back[1] = 18*6 +7;
					t->gfx_back[2] = 18*7 +6;
					t->gfx_back[3] = 18*7 +7;
					break;
				}
				
				     if (!adj[3] && !adj[6])            t->gfx_back[0] = 18*2 +4;
				else if (!adj[3] &&  adj[6])            t->gfx_back[0] = 18*1 +4;
				else if ( adj[3] && !adj[5] &&  adj[6]) t->gfx_back[0] = 18*2 +7;
				else if ( adj[3] && !adj[6])            t->gfx_back[0] = 18*2 +5;
				else                                    t->gfx_back[0] = 18*1 +5;
				
				     if (!adj[4] && !adj[6])            t->gfx_back[1] = 18*2 +6;
				else if (!adj[4] &&  adj[6])            t->gfx_back[1] = 18*1 +6;
				else if ( adj[4] && !adj[7] &&  adj[6]) t->gfx_back[1] = 18*0 +7;
				else if ( adj[4] && !adj[6])            t->gfx_back[1] = 18*2 +5;
				else                                    t->gfx_back[1] = 18*1 +5;
				
				     if (!adj[6] && !adj[3])            t->gfx_back[2] = 18*3 +4;
				else if (!adj[6])                       t->gfx_back[2] = 18*3 +5;
				else if (!adj[3] &&  adj[6] &&  adj[5]) t->gfx_back[2] = 18*3 +7;
				else if (!adj[3] || !adj[5])            t->gfx_back[2] = 18*1 +4;
				else                                    t->gfx_back[2] = 18*1 +5;
				
				     if (!adj[6] && !adj[4])            t->gfx_back[3] = 18*3 +6;
				else if (!adj[6])                       t->gfx_back[3] = 18*3 +5;
				else if (!adj[4] &&  adj[6] &&  adj[7]) t->gfx_back[3] = 18*1 +7;
				else if (!adj[4] || !adj[7])            t->gfx_back[3] = 18*1 +6;
				else                                    t->gfx_back[3] = 18*1 +5;
			}
			break;
		
		case TILE_EXTENDED:;
			TileExtension* e = t->extension;
			assert(e != NULL);
			
			switch (e->type) {
			
			case TE_STAIRS:;
				int use_ladder = abs(z - e->stairs.target.z) >= 2;
				if (e->stairs.dir == DIR_LEVELUP) {
					if (use_ladder) {
						t->gfx_back[0] = 18*6;
					} else {
						t->gfx_back[0] = 18*4;
					}
				} else {
					if (use_ladder) {
						t->gfx_back[0] = 18*6 +4;
					} else {
						t->gfx_back[0] = 18*4 +2;
					}
				}
							
				t->gfx_back[1] = t->gfx_back[0] +1;
				t->gfx_back[2] = t->gfx_back[0] + 18;
				t->gfx_back[3] = t->gfx_back[0] + 18 +1;
				break;
			
			case TE_SPAWN:
				t->gfx_back[0] = 18*4 + 12;
				t->gfx_back[1] = 18*4 + 13;
				t->gfx_back[2] = 18*5 + 12;
				t->gfx_back[3] = 18*5 + 13;
				break;
			
			case TE_TELEPORTER:
				t->gfx_back[0] = 18*8;
				t->gfx_back[1] = 18*8 +1;
				t->gfx_back[2] = 18*9;
				t->gfx_back[3] = 18*9 +1;
				t->n_frames_back = 8;
				break;
				
			case TE_TRIGGER:
				t->gfx_back[0] = 8;
				t->gfx_back[1] = 9;
				t->gfx_back[2] = 18 +8;
				t->gfx_back[3] = 18 +9;
				break;
				
			default:
				assert(!"cannot decorate unknown extended tile type");
			
			}
			
			break;
		
		default:
			assert(!"cannot decorate unknown tile type");
		
		}
	}
	
	for (int i = 0; i < m->object.count; i++) {
		MapObject* o = CARRAY_ELEM(&m->object,i,MapObject);
		
		switch (o->type) {
		
		case OBJ_OBSTACLE:
			o->image = 33;
			break;
		
		case OBJ_TREASURE_GOLD:
			o->image = 1;
			break;
		
		case OBJ_TREASURE_ITEM:
			o->image = 0;
			break;
		
		case OBJ_LEVER:
			o->image = 48;
			break;
		
		case OBJ_SOKOBOX:
			o->image = 32;
			break;
			
		// no image
		default:
		case OBJ_PICKUP:
			o->image = 1;
			break;
			
		}
	}
}

/*
 * Returns upper left corner of a tile bmp in the tile sheet
 */
static void gfx_tile_xy (MapDisplay* d, int sheet, int handle, int frames, int* x, int* y)
{
	assert(d != NULL);
	assert(x != NULL);
	assert(y != NULL);
	assert(frames > 0);
	
	int current_frame = d->anim_frame % frames;
	int tiles_w = d->tiles[sheet]->w / (TILE_SIZE / 2);
	*x = ((handle + current_frame * 2) % tiles_w) * TILE_SIZE / 2;
	*y = (handle / tiles_w) * TILE_SIZE / 2;
}

/*
 * Returns upper left corner of an object bmp in the object sheet
 */
static void gfx_obj_xy (MapDisplay* d, int handle, int* x, int* y)
{ 
	assert(d != NULL);
	assert(x != NULL);
	assert(y != NULL);
	assert(handle > 0);
	
	int sheet_w = d->objects->w / TILE_SIZE;
	*x = handle % sheet_w * TILE_SIZE;
	*y = handle / sheet_w * TILE_SIZE;
}

/*
 * Initializes the light member of a MapDisplay. 
 * capacity is the number of (memory-hogging) LightTables we may allocate.
 */
static void light_init (MapDisplay* d, int capacity)
{
	assert(d != NULL);
	assert(capacity >= 4); // 4 light tables are required to interpolate
	
	d->light.capacity = capacity;
	d->light.next = 0;
	
	int memsize = capacity * (sizeof (LightTable) + LIGHTTABLE_SIZE);
	d->light.mem = malloc (memsize);
	memset (d->light.mem, 0, memsize);
	for (int i = 0; i < capacity; i++) {
		d->light.mem[i].value = ((uint8_t*) (d->light.mem + capacity)) + 
		                        i * LIGHTTABLE_SIZE;
	}
	
	memsize = d->map->width * d->map->height * 
	          SUB_RES * SUB_RES * 
	          d->map->layers * sizeof (LightTable*);
	d->light.table = malloc (memsize);
	memset (d->light.table, 0, memsize);
}

/*
 * Frees light related resources in a MapDisplay
 */
static void light_cleanup (MapDisplay* d)
{
	assert(d != NULL);
	
	free (d->light.mem);
	free (d->light.table);
	
	memset (&d->light, 0, sizeof (Light));
}

/*
 * Same as TILE_INDEX, but with different tile resolution
 */
static int map_index_light (Map* m, int x, int y, int z)
{
	assert((x >= 0) && (x < m->width * SUB_RES));
	assert((y >= 0) && (y < m->height * SUB_RES));
	assert((z >= 0) && (z < m->layers));
	return z * m->width * SUB_RES * m->height * SUB_RES + 
	       y * m->width * SUB_RES + x;
}

/*
 * Returns the index of the given coordinates, which are light tile
 * units relative to the light table's center tile, in a light table's
 * value array.
 */
static int light_table_index (int x, int y)
{
	assert((x >= -LIGHTTABLE_WH/2) && (x <= LIGHTTABLE_WH/2));
	assert((y >= -LIGHTTABLE_WH/2) && (y <= LIGHTTABLE_WH/2));
	return (y+LIGHTTABLE_WH/2) * LIGHTTABLE_WH + (x+LIGHTTABLE_WH/2);
}

/*
 * Builds a light table from the given observer location (where) in
 * light tile units using a flood-fill algorithm on collision 
 * information from the Map. Memory is taken from d->light.mem. If
 * the memory space was previously used for another table, that table
 * is overwritten and its observer tile loses its light table. Older
 * tables get overwritten first.
 * Returns a pointer to the newly instated LightTable.
 */
static LightTable* light_make_table (MapDisplay* d, Coord where)
{
	// Figure out memory location, kill obsolete tables
	int memidx = d->light.next % d->light.capacity;
	if (d->light.next >= d->light.capacity) {
		Coord obs = d->light.mem[memidx].where;
		int idx = map_index_light (d->map, XYZ(obs));
		d->light.table[idx] = NULL;
	}
	d->light.next++;
	
	LightTable* t = &d->light.mem[memidx];
	int tblidx = map_index_light (d->map, XYZ(where));
	d->light.table[tblidx] = t;
	
	// everything that's not in line of sight is dark by default
	memset (t->value, 255, LIGHTTABLE_SIZE);
	
	// Fill table data using flood fill
	t->where = where;
	
	bool can_go (Coord from, Coord to)
	{
		#define BLOCKING(X,Y) TILE(d->map, (X) / SUB_RES, \
							           (Y) / SUB_RES, to.z).blocks_players
		
		//int dx = to.x - from.x;
		int dy = to.y - from.y;
		int bfrom = BLOCKING (from.x, from.y);
		int bto   = BLOCKING (to.x, to.y);
							  
		if (bto) { // to-tile is blocked
			if (dy == 1) {
				return 0;
			}
		}
		if (bfrom) { // from-tile is blocked
			// enables us to see north walls to a depth of 2 light tiles
			if (dy == -1) {
				if (!bto || BLOCKING (from.x, from.y + 1)) {
					return 0;
				}
			} else {
				return 0;
			}
		}
		
		// Prevents diagonal steps between 2 walls
		int bt1 = BLOCKING (from.x, to.y);
		int bt2 = BLOCKING (to.x, from.y);
		if (bt1 && bt2 && !bto) {
			return 0;
		}

		return 1;
	}
	
	void visit_handler (Coord coord, float distance)
	{
		int lti = light_table_index (coord.x - where.x, coord.y - where.y);
		uint8_t* ptr = &t->value[lti]; // pointer to darkness value at s.c
		
		// Store darkness value depending on distance from observer
		if (distance > FULLLIGHT_REACH) {
			*ptr = (distance - FULLLIGHT_REACH) * LIGHT_PER_TILE +.5;
		} else {
			*ptr = 0;
		}
	}
	
	// bounds in lightsquare units of visible light area
	int min_x = MAX(0, where.x - LIGHT_REACH);
	int min_y = MAX(0, where.y - LIGHT_REACH);
	int max_x = MIN((d->map->width  * SUB_RES) -1, where.x + LIGHT_REACH);
	int max_y = MIN((d->map->height * SUB_RES) -1, where.y + LIGHT_REACH);
	
	Rect space = { min_x, min_y, max_x, max_y, where.z };
	flood_fill (where, space, LIGHT_REACH, &can_go, &visit_handler);

	return t;
}

/**
 * Displays background effects. Effects in the foreground are drawn
 * together with map_display_fg.
 */ /*
static void map_display_effects (Map* m, BITMAP* target, Coord player)
{
	int xoffset = WIDTH/2 - player.x;
	int yoffset = HEIGHT/2 - player.y;
	for (int i = 0; i < MAX_EFFECTS; i++) {
		if ((m->effect[i].cooldown > 0) && (m->effect[i].where.z == player.z)) {
			effect_draw_bg (&m->effect[i], target, xoffset, yoffset - P_OFFSET);
		}
	}
}
*/

Coord actor_pxpos (Actor *actor)
{
	assert(actor != NULL);
	
	Coord c = { 
		actor->coord.x*TILE_SIZE + TILE_SIZE/2,
		actor->coord.y*TILE_SIZE + TILE_SIZE/2,
		actor->coord.z };
	
	if (actor->action.type == ACTION_MOVE) {
		int px = TILE_SIZE * actor->action.cooldown / COOLDOWN_MOVE;
		switch (actor->dir) {
		case DIR_UP:    c.y += px; break;
		case DIR_RIGHT: c.x -= px; break;
		case DIR_DOWN:  c.y -= px; break;
		case DIR_LEFT:  c.x += px; break;
		default: assert(0);
		}
	}

	return c;
}

#ifdef TEST_MAP_DISPLAY
#include <stdio.h>
#include "dig.h"

void test_gfx_tile_xy (MapDisplay* d, int ts, int handle, int expect_x, int expect_y) 
{
	assert(d->tileset[ts]->w == (18 * (TILE_SIZE/2)));
	
	fprintf (stderr, "test_gfx_tile_xy: handle %d should give x %d y %d...", handle, expect_x, expect_y);
	int x, y;
	gfx_tile_xy (d, ts, handle, 1, &x, &y);
	assert(x == expect_x);
	assert(y == expect_y);
	fprintf (stderr, " Ok\n");
}

BITMAP* buffer;
int quit;

void draw_grid(int xoffset, int yoffset, int color)
{
	drawing_mode(DRAW_MODE_TRANS, NULL, 0, 0);
	set_trans_blender(0,0,0,45);
	for(int i = 0; i < 30; i++) {
		int xx = xoffset + i * LTILE_SIZE;
		int yy = yoffset + i * LTILE_SIZE;
		hline(buffer, xoffset, yy, xoffset + 30 * LTILE_SIZE, color);
		vline(buffer, xx, yoffset, yoffset + 30 * LTILE_SIZE, color);
	}
	drawing_mode(DRAW_MODE_SOLID, NULL, 0, 0);
}

void draw_squares(int xoffset, int yoffset, Coord sq[4], int color)
{
	drawing_mode(DRAW_MODE_TRANS, NULL, 0, 0);
	set_trans_blender(0,0,0,80);
	for(int i = 0; i < 4; i++) {
		int xx = xoffset + sq[i].x * LTILE_SIZE;
		int yy = yoffset + sq[i].y * LTILE_SIZE;
		rect(buffer, xx, yy, xx+LTILE_SIZE, yy+LTILE_SIZE, color);
	}
	drawing_mode(DRAW_MODE_SOLID, NULL, 0, 0);
}

void flip()
{
	stretch_blit(buffer, screen, 0, 0, buffer->w, buffer->h, 0, 0, SCREEN_W, SCREEN_H);
	clear_bitmap (buffer); 
}

volatile int ticks = 0; 
void timer(void)
{
	ticks++;
}

void load_allegro ()
{
	allegro_init();
	install_keyboard();
	install_timer();
	install_mouse();
	enable_hardware_cursor (); // TODO: check capabilities?
	set_color_depth(32);
	set_alpha_blender();
	set_gfx_mode(GFX_AUTODETECT_WINDOWED, 640, 480, 0, 0);
	buffer = create_bitmap(320, 240);
	install_int_ex(timer, BPS_TO_TIMER(10));
}


void main_loop (MapDisplay* display)
{	
	ticks = 0;
	int px, py;
	int tx, ty;
	int changed = 0;
	
	px = 20;
	py = 20;
	tx = 160;
	ty = 50;
	
	while (!key[KEY_ESC]) {
		changed = 0;
		while (ticks > 0) {
			if (key[KEY_LEFT])  { px--; changed = 1; }
			if (key[KEY_RIGHT]) { px++; changed = 1; }
			if (key[KEY_UP])    { py--; changed = 1; }
			if (key[KEY_DOWN])  { py++; changed = 1; }
			if (key[KEY_A])     { tx--; changed = 1; }
			if (key[KEY_S])     { tx++; changed = 1; }
			if (key[KEY_W])     { ty--; changed = 1; }
			if (key[KEY_R])     { ty++; changed = 1; }
			
			display->anim_frame ++;
			ticks --;
		}
		
		int x, y;
		map_display_bg (display, buffer, (Coord) {px, py, 0}, &x, &y);
		map_display_fg (display, buffer, (Coord) {px, py, 0});
		int d = map_display_get_darkness_1 (display, (Coord) {px, py, 0}, (Coord) {tx, ty, 0}, 1);
		textprintf_right_ex(buffer, font, 310, 10, makecol(0, 255, 0), -1, "%d", d);
		textprintf_ex(buffer, font, 10, 10, makecol(0, 255, 0), -1, "obs=%d,%d", px, py);
		textprintf_ex(buffer, font, 10, 20, makecol(0, 255, 0), -1, "tgt=%d,%d", tx, ty);
		
		if (changed) {
			fprintf(stderr, "-------------------------------\n");
			fprintf(stderr, "obsct %2d,%2d   %2d,%2d  obscp %3d,%3d   %3d,%3d\n", debugnfo.obsct[0].x, debugnfo.obsct[0].y, debugnfo.obsct[1].x, debugnfo.obsct[1].y, debugnfo.obscp[0].x, debugnfo.obscp[0].y, debugnfo.obscp[1].x, debugnfo.obscp[1].y);
			fprintf(stderr, "      %2d,%2d   %2d,%2d        %3d,%3d   %3d,%3d\n", debugnfo.obsct[2].x, debugnfo.obsct[2].y, debugnfo.obsct[3].x, debugnfo.obsct[3].y, debugnfo.obscp[2].x, debugnfo.obscp[2].y, debugnfo.obscp[3].x, debugnfo.obscp[3].y);
			fprintf(stderr, "tgtct %2d,%2d   %2d,%2d  tgtcp %3d,%3d   %3d,%3d\n", debugnfo.tgtct[0].x, debugnfo.tgtct[0].y, debugnfo.tgtct[1].x, debugnfo.tgtct[1].y, debugnfo.tgtcp[0].x, debugnfo.tgtcp[0].y, debugnfo.tgtcp[1].x, debugnfo.tgtcp[1].y);
			fprintf(stderr, "      %2d,%2d   %2d,%2d        %3d,%3d   %3d,%3d\n", debugnfo.tgtct[2].x, debugnfo.tgtct[2].y, debugnfo.tgtct[3].x, debugnfo.tgtct[3].y, debugnfo.tgtcp[2].x, debugnfo.tgtcp[2].y, debugnfo.tgtcp[3].x, debugnfo.tgtcp[3].y);
			fprintf(stderr, " - \n");
			fprintf(stderr, "ptval %3d %3d   %3d %3d\n", debugnfo.ptval[0], debugnfo.ptval[1], debugnfo.ptval[4], debugnfo.ptval[5]);
			fprintf(stderr, "      %3d %3d   %3d %3d\n", debugnfo.ptval[2], debugnfo.ptval[3], debugnfo.ptval[6], debugnfo.ptval[7]);
			fprintf(stderr, "      %3d %3d   %3d %3d\n", debugnfo.ptval[8], debugnfo.ptval[9], debugnfo.ptval[12], debugnfo.ptval[13]);
			fprintf(stderr, "      %3d %3d   %3d %3d\n", debugnfo.ptval[10], debugnfo.ptval[11], debugnfo.ptval[14], debugnfo.ptval[15]);
			fprintf(stderr, " - \n");
			fprintf(stderr, "weigt %3d %3d   %3d %3d\n", debugnfo.wgt[0], debugnfo.wgt[1], debugnfo.wgt[4], debugnfo.wgt[5]);
			fprintf(stderr, "      %3d %3d   %3d %3d\n", debugnfo.wgt[2], debugnfo.wgt[3], debugnfo.wgt[6], debugnfo.wgt[7]);
			fprintf(stderr, "      %3d %3d   %3d %3d\n", debugnfo.wgt[8], debugnfo.wgt[9], debugnfo.wgt[12], debugnfo.wgt[13]);
			fprintf(stderr, "      %3d %3d   %3d %3d\n", debugnfo.wgt[10], debugnfo.wgt[11], debugnfo.wgt[14], debugnfo.wgt[15]);
		}
		
		draw_grid(x, y, makecol(255, 255, 255));
		draw_squares(x, y, debugnfo.obsct, makecol(100, 200, 0));
		draw_squares(x, y, debugnfo.tgtct, makecol(90, 20, 255));
		
		putpixel(buffer, px+x, py+y, makecol(255, 255, 255));
		putpixel(buffer, tx+x, ty+y, makecol(255, 0, 255));
		flip();
		
		while (ticks <= 0)
			rest(1);
	}
}

int main ()
{
	Layout layout;
	layout_init (&layout, 30, 30, 1, 1000, 1000);
	dig_init (&layout);
	
	int prev [4];
	Rect room = { 1, 1, 13, 13, 0 };
	layout_floor_rect (&layout, &room);
	/*
	prev[0] = dig_room (8, 15, prev, 0);
	prev[2] = dig_room (9, 7, prev, 1);
	prev[1] = dig_room (10, 5, prev, 1 );
	prev[0] = prev[2];
	prev[3] = dig_room (20, 14, prev, 2 );
	prev[0] = prev[3];
	prev[0] = dig_room (7, 13, prev, 1 );
	prev[1] = dig_room (9, 15, prev, 1 );
	dig_room (10, 10, prev, 4 );*/
	dig_cleanup ();
	
	Map map;
	map_init (&map, &layout);
	MapDisplay display;
	map_display_init (&display, &map);
	
	quit = 0;
	load_allegro ();

	BITMAP* tileset = load_bitmap ("gfx/tiles0.tga", NULL);
	assert(tileset != NULL);
	
	for (int z = 0; z < map.layers; z++) display.tileset[z] = tileset;
		/*
	test_gfx_tile_xy (&display, 0, 0,      0 * TILE_SIZE/2, 0 * TILE_SIZE/2);
	test_gfx_tile_xy (&display, 0, 7,      7 * TILE_SIZE/2, 0 * TILE_SIZE/2);
	test_gfx_tile_xy (&display, 0, 18*4,   0 * TILE_SIZE/2, 4 * TILE_SIZE/2);
	test_gfx_tile_xy (&display, 0, 18*2+6, 6 * TILE_SIZE/2, 2 * TILE_SIZE/2);
	test_gfx_tile_xy (&display, 0, 18*6+1, 1 * TILE_SIZE/2, 6 * TILE_SIZE/2);
		*/
	main_loop (&display);
	
	destroy_bitmap (tileset);
	
	map_display_cleanup (&display);
	map_cleanup (&map);
	layout_cleanup (&layout);
	return 0;
}
END_OF_MAIN()

#endif /* TEST_MAP_DISPLAY */
